W11. Priority Queues and Heaps

Author

Nikolai Kudasov

Published

March 31, 2026

1. Theory

1.1 Priority Queues
1.1.1 Motivation

In many real applications, work items must be processed in order of importance rather than in the order they arrive. For example, an operating system scheduler might always run the highest-priority process first, or a network router might forward the most critical packets ahead of ordinary traffic. In a static setting — where all items are known in advance — you could simply sort them once and process them in order. But in a dynamic setting, new requests arrive continuously while processing is ongoing. Sorting from scratch after every insertion is far too slow.

The abstract data type designed for this scenario is the priority queue: a collection that allows efficient insertion of new items and efficient retrieval (and removal) of the item with the highest (or lowest) priority.

1.1.2 Priority Queue ADT

A max-priority queue supports the following operations:

  • INSERT(x, p) — insert element with priority into the queue.
  • MAXIMUM() — return (but do not remove) the element with maximum priority.
  • EXTRACT-MAX() — remove and return the element with maximum priority.
  • INCREASE-KEY(x, p') — increase the priority of element to (requires ). This operation is critical for graph algorithms such as Dijkstra’s shortest-path algorithm and Prim’s minimum spanning tree algorithm, which need to reprioritize already-queued nodes.
  • UNION(Q_1, Q_2) (optional) — merge two priority queues into one. Useful in parallel or functional settings.

A min-priority queue is the symmetric counterpart, offering MINIMUM(), EXTRACT-MIN(), and DECREASE-KEY() in place of the max versions.

1.1.3 Implementation Options

Different underlying data structures yield different asymptotic complexities for the priority-queue operations. The table below summarises the main options (see Cormen et al. 2022, §6.1 and Cormen et al. 2009, §19):

Structure INSERT EXTRACT-MAX INCREASE-KEY UNION
Unsorted list
Sorted list
Binary search tree —
Binary heap —
Binomial heap amort.
Fibonacci heap amort. amort.

The binary heap is the standard practical choice: it achieves for all three core operations, supports an elegant in-place array representation, and leads directly to the heapsort algorithm. The Fibonacci heap has superior theoretical amortized bounds and is theoretically important for graph algorithms, but its constant factors make it less attractive in practice.

1.2 Complete Binary Trees
1.2.1 Definition

A complete binary tree is a binary tree satisfying two conditions:

  1. Every level except possibly the last is completely filled (i.e., every non-leaf node on those levels has exactly two children).
  2. All nodes on the last level are as far left as possible — there are no gaps to the left of any node on the bottom row.

The height of a complete binary tree with nodes is , because each level at most doubles the number of nodes. This logarithmic height is exactly what makes heap operations efficient.

A common mistake is to confuse “complete” with “perfect” (every level fully filled) or “full” (every node has 0 or 2 children). A complete binary tree need not be perfect, but it must have all bottom-level nodes pushed to the left.

1.2.2 Array Representation

A complete binary tree with nodes can be stored compactly in an array of length using level-order numbering: nodes are assigned indices by reading the tree level by level, left to right. This gives the following navigation formulas for node at index (0-based):

Because the tree is complete, every node with index is a leaf: it has no children stored in the array. Nodes at indices through are internal nodes.

Example. For the tree with 12 nodes numbered 0–11:

0 1 2 3 4 5 6 7 8 9 10 11
99 19 36 17 6 25 18 2 7 4 5 1

Navigation check: node at index 4 (value 6) has left child at (value 4) and right child at (value 5). Node at index 11 (value 1) has parent at (value 25). ✓

1.3 Binary Heaps
1.3.1 Heap Property

A binary max-heap is a complete binary tree in which every node satisfies the max-heap property:

Equivalently, in the array representation: for every .

A direct consequence is that the root always holds the maximum key of the entire heap. A binary min-heap satisfies and keeps the minimum at the root.

Two common violations to watch for:

  • A child is larger than its parent — this breaks the max-heap property at that edge.
  • A node is missing where a left child should appear before a right child on the bottom level — this breaks the completeness requirement (not a valid complete binary tree at all).
1.3.2 MAX-HEAPIFY

The fundamental repair procedure is MAX-HEAPIFY(A, i). It assumes the subtrees rooted at the left and right children of already satisfy the max-heap property, and it pushes the element at index downward until the heap property is restored at (Cormen et al. 2022, §6.2):

MAX-HEAPIFY(A, i)
1  l = LEFT(i)           // 2i + 1
2  r = RIGHT(i)          // 2i + 2
3  if l <= A.heap-size and A[l] > A[i]
4      largest = l
5  else largest = i
6  if r <= A.heap-size and A[r] > A[largest]
7      largest = r
8  if largest != i
9      exchange A[i] with A[largest]
10     MAX-HEAPIFY(A, largest)

The idea: find the largest value among node and its (up to two) children. If already holds the largest value, the subtree is already a valid heap and we stop. Otherwise, swap with the larger child and recurse on that child’s position, because the swap may have placed a smaller value into a subtree that previously satisfied the heap property.

Complexity. At each level of the recursion, we do work. The recursion descends at most one path from to a leaf, so the depth is where is the height of the subtree rooted at . In the worst case (the root, ), this is .

1.3.3 BUILD-MAX-HEAP

Given an arbitrary array of elements, we can convert it into a max-heap in-place using BUILD-MAX-HEAP (Cormen et al. 2022, §6.3):

BUILD-MAX-HEAP(A, n)
1  A.heap-size = n
2  for i = floor(n/2) - 1 downto 0
3      MAX-HEAPIFY(A, i)

We call MAX-HEAPIFY on every internal node, starting from the lowest internal node () up to the root (index 0). We start from the bottom because MAX-HEAPIFY requires the children’s subtrees to already be valid heaps; when we process node from the bottom up, all nodes at larger indices (deeper in the tree) have already been heapified.

Nodes at indices through are leaves. A single-node subtree is trivially a valid heap, so there is no work to do for leaves.

Complexity analysis. Naively, each of calls to MAX-HEAPIFY costs , giving . However, a tighter analysis shows the true cost is .

The key observation is that most calls to MAX-HEAPIFY are made on subtrees of small height. The number of nodes at height in a complete binary tree of nodes is at most . Since MAX-HEAPIFY on a subtree of height costs :

The last step uses the identity , which follows from differentiating the geometric series and evaluating at .

Therefore BUILD-MAX-HEAP runs in time.

1.3.4 EXTRACT-MAX

To remove and return the maximum (root) of the heap (Cormen et al. 2022, §6.5):

MAX-HEAP-EXTRACT-MAX(A)
1  max = MAX-HEAP-MAXIMUM(A)      // save root value
2  A[1] = A[A.heap-size]          // move last element to root (1-based indexing)
3  A.heap-size = A.heap-size - 1
4  MAX-HEAPIFY(A, 1)              // restore heap property
5  return max

The trick is to move the last element of the array to the root position (filling the hole left by removing the maximum) and then calling MAX-HEAPIFY to sink it to its correct position. This avoids any shifting. Since MAX-HEAPIFY costs , so does EXTRACT-MAX.

1.3.5 INCREASE-KEY and INSERT

INCREASE-KEY works by updating the key and then bubbling up: after increasing a key, the node may become larger than its parent, violating the heap property going upward. We fix this by repeatedly swapping the node with its parent as long as the parent is smaller (Cormen et al. 2022, §6.5):

MAX-HEAP-INCREASE-KEY(A, x, k)
1  if k < x.key
2      error "new key is smaller than current key"
3  x.key = k
4  find the index i in array A where object x occurs
5  while i > 1 and A[PARENT(i)].key < A[i].key
6      exchange A[i] with A[PARENT(i)]
7      i = PARENT(i)

The bubble-up traverses at most the height of the tree, costing .

INSERT is implemented by appending a new element with key at the end of the array (making the heap one larger while trivially satisfying the heap property), then calling INCREASE-KEY to raise it to the desired key:

MAX-HEAP-INSERT(A, x, n)
1  if A.heap-size == n
2      error "heap overflow"
3  A.heap-size = A.heap-size + 1
4  k = x.key
5  x.key = -∞             // ensures heap property is not violated yet
6  A[A.heap-size] = x
7  MAX-HEAP-INCREASE-KEY(A, x, k)

Assigning on line 5 guarantees that the new node is smaller than everything already in the heap, so appending it never violates the heap property. INCREASE-KEY then raises it to the correct value. The total cost is .

1.4 Heapsort

Heapsort sorts an array in-place by combining BUILD-MAX-HEAP and repeated extraction (Cormen et al. 2022, §6.4):

HEAPSORT(A, n)
1  BUILD-MAX-HEAP(A, n)
2  for i = n downto 2
3      exchange A[1] with A[i]     // move current max to its final sorted position
4      A.heap-size = A.heap-size - 1
5      MAX-HEAPIFY(A, 1)

How it works. After BUILD-MAX-HEAP, A[1] holds the largest element. We swap it with A[n] (the last position in the array, which is its correct sorted position), shrink the heap by one, and call MAX-HEAPIFY to restore the heap property. Repeating this times extracts elements in descending order, placing them in positions of the array. The result is a sorted array.

Properties of heapsort:

Property Value
Time complexity (worst case)
Extra space — in-place with iterative MAX-HEAPIFY
Stable? No
Deterministic? Yes

The bound comes from the build phase plus calls to MAX-HEAPIFY, each costing .

Compared to merge sort: heapsort uses only extra memory (merge sort needs ), but heapsort tends to be less cache-friendly because MAX-HEAPIFY accesses memory at positions , , , which can be far apart in large arrays, causing more cache misses than merge sort’s sequential access patterns.

1.5 Fibonacci Heaps

Fibonacci heaps (Cormen et al. 2009, §19) provide an efficient implementation of mergeable priority queues with superior amortized complexity. They are theoretically important for graph algorithms such as Dijkstra’s (with total time) and Prim’s (with the same bound).

1.5.1 Structure

A Fibonacci heap is a collection (forest) of min-heap-ordered trees. Unlike binary heaps, the trees need not be binary or complete. The heap maintains:

  • A root list: a circular doubly linked list of the root nodes of all trees.
  • A pointer H.min: points to the root with the minimum key among all roots.
  • A count H.n: the total number of nodes.

Each node stores: x.key, x.degree (number of children), x.mark (a boolean indicating whether has lost a child since it last became a non-root node), pointers to parent, one child, and left/right siblings in the doubly linked list.

The mark field is the key mechanism that keeps trees from becoming too tall, which would degrade EXTRACT-MIN performance.

1.5.2 Insertion and Union

Insertion is : create a new single-node tree and splice it into the root list, updating H.min if necessary.

FIB-HEAP-INSERT(H, x)
1  x.degree = 0; x.p = NIL; x.child = NIL; x.mark = FALSE
2  if H.min == NIL
3      create root list for H containing just x; H.min = x
4  else insert x into H's root list
5      if x.key < H.min.key then H.min = x
6  H.n = H.n + 1

Union is also : simply concatenate the two root lists (a pointer splice in the doubly linked lists) and update H.min to be the smaller of the two existing minima.

FIB-HEAP-UNION(H1, H2)
1  H = MAKE-FIB-HEAP()
2  H.min = H1.min
3  concatenate root list of H2 with root list of H
4  if H1.min == NIL or (H2.min != NIL and H2.min.key < H1.min.key)
5      H.min = H2.min
6  H.n = H1.n + H2.n
7  return H

No tree restructuring is done during insertion or union — all work is deferred to EXTRACT-MIN.

1.5.3 Extract-Min and Consolidation

EXTRACT-MIN is the most complex operation:

  1. Move all children of the minimum node to the root list (they become new roots).
  2. Remove the minimum node from the root list.
  3. Consolidate: reorganize the root list so that no two roots have the same degree. This is done by repeatedly linking two roots of equal degree (making the one with the larger key a child of the one with the smaller key) until all roots have distinct degrees.
FIB-HEAP-EXTRACT-MIN(H)
1  z = H.min
2  if z != NIL
3      for each child x of z: add x to root list, x.p = NIL
4      remove z from root list
5      if z == z.right then H.min = NIL
6      else H.min = z.right; CONSOLIDATE(H)
7      H.n = H.n - 1
8  return z

The CONSOLIDATE procedure uses an auxiliary array indexed by degree, where is the maximum possible degree of any node. It scans the root list, and whenever two roots of the same degree are found, links them (smaller key becomes parent), incrementing the degree to and repeating until no two roots share a degree.

Complexity. In the worst case, EXTRACT-MIN costs (if the root list is huge after many insertions). However, the amortized cost is : the consolidation “pays back” the work done by many cheap insertions. Formally, a potential-function argument shows this amortized bound holds.

1.5.4 Decrease-Key and Cascading Cut

DECREASE-KEY decreases the key of a node to . If this violates the min-heap property (i.e., becomes smaller than its parent ), we cut from its parent and move it to the root list. To prevent trees from becoming arbitrarily deep (which would hurt EXTRACT-MIN), we use the cascading cut mechanism:

  • When a node loses a child for the first time, mark it (y.mark = TRUE).
  • When a marked node loses a second child, cut itself from its parent and move it to the root list (unmarking it), then apply the same rule to ’s parent. This cascades up until either an unmarked node or the root is reached.
FIB-HEAP-DECREASE-KEY(H, x, k)
1  if k > x.key then error
2  x.key = k; y = x.p
3  if y != NIL and x.key < y.key
4      CUT(H, x, y); CASCADING-CUT(H, y)
5  if x.key < H.min.key then H.min = x

CUT(H, x, y)
1  remove x from child list of y, decrement y.degree
2  add x to root list of H; x.p = NIL; x.mark = FALSE

CASCADING-CUT(H, y)
1  z = y.p
2  if z != NIL
3      if y.mark == FALSE then y.mark = TRUE
4      else CUT(H, y, z); CASCADING-CUT(H, z)

Complexity. The worst-case cost is (a long cascading chain), but the amortized cost is . Intuitively, every cascading cut is “pre-paid” by the earlier DECREASE-KEY that caused the mark to be set.

1.5.5 Amortized Bounds Summary

The full table of amortized time bounds for Fibonacci heaps (Cormen et al. 2009, §19):

Operation Amortized time
FIB-HEAP-INSERT
FIB-HEAP-MINIMUM
FIB-HEAP-UNION
FIB-HEAP-EXTRACT-MIN
FIB-HEAP-DECREASE-KEY
FIB-HEAP-DELETE

Important caveat: Fibonacci heaps have large constant factors and complex pointer manipulation. In practice, binary heaps or -ary heaps often outperform them on real inputs. The theoretical advantage of Fibonacci heaps materialises mainly when in graph algorithms (where DECREASE-KEY is called many more times than EXTRACT-MIN).

2. Definitions

  • Priority queue: An abstract data type maintaining a collection of elements with associated priorities, supporting efficient insertion and retrieval/removal of the element with maximum (or minimum) priority.
  • Max-priority queue: A priority queue whose operations (MAXIMUM, EXTRACT-MAX, INCREASE-KEY) operate on the maximum-priority element.
  • Min-priority queue: A priority queue whose operations (MINIMUM, EXTRACT-MIN, DECREASE-KEY) operate on the minimum-priority element.
  • Complete binary tree: A binary tree in which every level except possibly the last is fully filled, and all nodes on the last level are as far left as possible.
  • Binary max-heap: A complete binary tree satisfying the max-heap property: every node’s key is greater than or equal to the keys of its children.
  • Binary min-heap: A complete binary tree satisfying the min-heap property: every node’s key is less than or equal to the keys of its children.
  • Heap property: The invariant that every parent key is (max-heap) or (min-heap) all its children’s keys.
  • Heap-size: The number of valid elements currently stored in the heap array (may be less than the array’s allocated capacity).
  • MAX-HEAPIFY: A procedure that restores the max-heap property at node , assuming its subtrees are already valid max-heaps, by sinking the element at downward.
  • BUILD-MAX-HEAP: A procedure that converts an arbitrary array into a max-heap in time by calling MAX-HEAPIFY on every internal node from bottom to top.
  • EXTRACT-MAX: A heap operation that removes and returns the maximum element (root) in time.
  • INCREASE-KEY: A heap operation that raises a node’s key and restores the heap property by bubbling the node upward in time.
  • Heapsort: An in-place, deterministic, comparison sort that builds a max-heap and then repeatedly extracts the maximum.
  • Fibonacci heap: A data structure implementing a mergeable priority queue as a forest of min-heap-ordered trees with lazy restructuring, achieving amortized time for INSERT, MINIMUM, UNION, and DECREASE-KEY, and amortized time for EXTRACT-MIN and DELETE.
  • Root list: In a Fibonacci heap, the circular doubly linked list of all tree roots.
  • Degree of a node: The number of children of a node in a Fibonacci heap.
  • Mark: A boolean attribute of a Fibonacci heap node indicating whether it has lost one child since it last became a non-root. Used to trigger cascading cuts.
  • CUT: The Fibonacci heap operation of removing a node from its parent’s child list and adding it to the root list.
  • CASCADING-CUT: A recursive procedure that cuts a marked node from its parent and propagates upward, ensuring trees do not become too deep.
  • CONSOLIDATE: A Fibonacci heap subroutine called during EXTRACT-MIN that restructures the root list so no two roots have the same degree.

3. Formulas

  • Node index navigation (0-based array):
    • Left child of :
    • Right child of :
    • Parent of ():
  • Leaf range: nodes at indices through are leaves.
  • Height of complete binary tree:
  • Number of nodes at height :
  • BUILD-MAX-HEAP cost:
  • Heapsort time complexity: — from build plus calls to MAX-HEAPIFY.
  • Heapsort space complexity: extra memory (in-place, with iterative MAX-HEAPIFY).

4. Practice

4.1. Analyze and Disprove WeirdMedian (Problem Set 9, Task 1)

Consider the following algorithm on an unsorted array :

WEIRD-MEDIAN(A, n):
  BUILD-MAX-HEAP(A)
  s := ⌊n/2⌋
  BUILD-MAX-HEAP(A[s..n-1])
  return A[s]

(a) Compute the asymptotic running time of WEIRD-MEDIAN in -notation.

(b) Determine whether WEIRD-MEDIAN always returns the median. Prove it, or give a counterexample.

(c) Consider WEIRD-MEDIAN-ASC: before the first BUILD-MAX-HEAP, sort in ascending (nondecreasing) order. Does this modified version always return the median?

(d) Consider WEIRD-MEDIAN-DESC: before the first BUILD-MAX-HEAP, sort in descending (nonincreasing) order. Does this modified version always return the median? For even , either of the two middle elements is a valid median.

Click to see the solution

(a) Running time of WEIRD-MEDIAN.

The first BUILD-MAX-HEAP operates on all elements and takes . The second call operates on , which contains elements and therefore also takes . The total is .

Answer: .

(b) Does WEIRD-MEDIAN always return the median? No.

Counterexample. Let . The true median is .

  1. BUILD-MAX-HEAP produces (5 at root; its children are 3 and 4; children of 3 are 1 and 2).
  2. , so the subarray is .
  3. BUILD-MAX-HEAP: already a valid max-heap (4 is the root, children are 1 and 2).
  4. .

The algorithm returns , which is not the median.

(c) Does WEIRD-MEDIAN-ASC always return the median? No.

Counterexample. Let . Already sorted ascending; the median is .

  1. BUILD-MAX-HEAP gives, for example, .
  2. ; subarray .
  3. BUILD-MAX-HEAP gives (6 floats to the root).
  4. .

The algorithm returns , which is not the median.

(d) Does WEIRD-MEDIAN-DESC always return the median? Yes.

Proof. After sorting in descending order, .

A sorted-descending array is already a valid max-heap: every parent by the sorted order. Therefore the first BUILD-MAX-HEAP does nothing — the array is unchanged.

Set . The subarray contains exactly elements. Because the full array is sorted descending, these are the smallest elements of . The second BUILD-MAX-HEAP rearranges into a max-heap, placing its maximum at index :

Now consider the two cases:

  • odd. , so has elements. The maximum among the smallest elements of a sorted array of size is the element at rank in ascending order — exactly the median.
  • even. , so has elements. The maximum of the smallest elements is the lower median, which is a valid median by the problem statement.

In both cases WEIRD-MEDIAN-DESC returns the median.

4.2. Analyze a -ary Min-Heap (Problem Set 9, Task 2)

A -ary min-heap () is a complete -ary tree stored in an array in level order (root at index 0), satisfying the min-heap property: every parent key each child key.

(a) Derive formulas for the parent index of node , and the index of the -th child () of node .

(b) Give pseudocode for MIN-HEAPIFY.

(c) Analyze the worst-case running time of INSERT on a -ary min-heap of nodes.

(d) Analyze the worst-case running time of EXTRACT-MIN on a -ary min-heap of nodes.

(e) For and node index , write the indices of all children of .

(f) Compute the asymptotic number of nodes in a -ary heap of height . Express complexities in -notation in terms of and (or and where appropriate).

Click to see the solution

(a) Index formulas.

In level-order numbering, node has children at positions . If node is the -th child of parent , then , giving .

  • Parent of node :
  • -th child of node ():

Sanity check with : parent of node 3 is ; children of node 0 are indices 1 and 2. These match the standard binary heap formulas.

(b) Pseudocode for MIN-HEAPIFY.

MIN-HEAPIFY_d(A, i):
  smallest := i
  for j := 1 to d:
    c := d * i + j
    if c < A.heap-size and A[c] < A[smallest]:
      smallest := c
  if smallest != i:
    swap A[i] and A[smallest]
    MIN-HEAPIFY_d(A, smallest)

We scan all children of node to find the one with the smallest key. If that child is smaller than , we swap and recurse on the child. Each recursive call descends one level, and the recursion terminates when the node is already smaller than all its children or when we reach a leaf.

(c) Worst-case running time of INSERT.

INSERT appends the new element at the end of the array and then repeatedly compares it with its parent, swapping if the new element is smaller (bubble-up). Each step takes . The height of a -ary heap with nodes is (since gives ), so there are at most bubble-up steps.

Worst-case: .

(d) Worst-case running time of EXTRACT-MIN.

EXTRACT-MIN removes the root, places the last array element at the root, decrements the heap size, and calls MIN-HEAPIFY. Each call to MIN-HEAPIFY scans all children of the current node to find the minimum — this costs per level. Since the height is , the total work is .

Worst-case: .

(e) Children of node for .

Applying the formula for :

Children of node 5: indices 21, 22, 23, 24.

(f) Number of nodes in a -ary heap of height .

Level (where the root is level 0) contains at most nodes for . Summing over all levels:

The dominant term is , which is .

Asymptotic number of nodes: .

4.3. Frequency-Based Fibonacci Heap Filter (Problem Set 9, Task 3)

You are given an array of integers and an integer . Process elements from left to right, maintaining priorities for distinct values seen so far. For a value with current occurrence count , define:

Use a Fibonacci min-heap over currently seen values. After processing each element, if the heap contains more than elements, perform one EXTRACT-MIN (which removes the element seen most frequently so far). At the end, output the sum of all elements remaining in the heap.

(a) Propose an algorithm (pseudocode or clear steps). Specify the auxiliary data structure you use alongside the Fibonacci heap.

(b) Derive the asymptotic worst-case time complexity in -notation in terms of and , using standard amortized bounds for Fibonacci-heap operations and expected-time bounds for hash-table operations.

Click to see the solution

(a) Algorithm.

We maintain a hash table node_map mapping each distinct value to a pair . Storing the node pointer allows us to call DECREASE-KEY directly in amortized time without searching for in the heap.

FREQ-HEAP(A, n, k):
  H        := empty Fibonacci min-heap
  node_map := empty hash table      // x -> (freq, heap_node_ptr)

  for i := 0 to n-1:
    x := A[i]
    if x not in node_map:
      ptr := H.INSERT(x, key = -1)   // priority = -freq = -1
      node_map[x] := (1, ptr)
    else:
      (f, ptr) := node_map[x]
      f := f + 1
      H.DECREASE-KEY(ptr, -f)        // new key = -f (more negative = higher priority)
      node_map[x] := (f, ptr)
    if H.size > k:
      v := H.EXTRACT-MIN()           // removes the most-frequent element
      delete node_map[v.value]

  result := 0
  for each node v remaining in H:
    result := result + v.value
  return result

Why this works. The Fibonacci min-heap stores keys equal to . The element with the most negative key (i.e., the most frequent) is always at the minimum, so EXTRACT-MIN correctly removes the most-frequent element when the heap exceeds entries. DECREASE-KEY is called (not increase-key) because each new occurrence makes the key more negative.

(b) Complexity analysis.

We execute exactly main iterations. In each iteration:

  • Hash table lookup / update: expected.
  • Fib-INSERT (first occurrence of ): amortized.
  • Fib-DECREASE-KEY (repeat occurrence of ): amortized.
  • Fib-EXTRACT-MIN (only when heap size ): amortized, because at the moment of the call the heap contains at most elements.

There are at most total EXTRACT-MIN calls (each removes one distinct element, and there are at most distinct elements). Each costs .

Total cost:

Worst-case time complexity: .

4.4. Build a Max-Heap from an Array (Lecture 9, Task 1)

Build a max-heap from the following array (0-based indexing):

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4 1 3 2 16 9 10 14 8 7 5 6 11 13 12 17
Click to see the solution

Key Concept: BUILD-MAX-HEAP calls MAX-HEAPIFY on all internal nodes from index down to 0.

With , internal nodes are at indices 0–7.

  1. MAX-HEAPIFY(A, 7): Node 7 has value 14, left child at index 15 has value 17. Since , swap: , . No further recursion (index 15 is a leaf).

    Array after: ...14... 17...14 (positions 7 and 15 swapped).

  2. MAX-HEAPIFY(A, 6): Node 6 has value 10, left child index 13 = 13, right child index 14 = 12. Largest child is 13 (value 13). , swap: , . Node 13 is a leaf. Done.

  3. MAX-HEAPIFY(A, 5): Node 5 has value 9, left child index 11 = 6, right child index 12 = 11. Largest child is 11 (value 11). , swap: , . Node 11 is a leaf. Done.

  4. MAX-HEAPIFY(A, 4): Node 4 has value 16, left child index 9 = 7, right child index 10 = 5. Largest is 16 (the node itself). No swap needed.

  5. MAX-HEAPIFY(A, 3): Node 3 has value 2, left child index 7 = 17, right child index 8 = 8. Largest is 17 (index 7). Swap: , . Recurse on index 7: node 7 has value 2, left child index 15 = 14, right child doesn’t exist (). , swap: , . Done.

  6. MAX-HEAPIFY(A, 2): Node 2 has value 3, left child index 5 = 11, right child index 6 = 13. Largest is 13 (index 6). Swap: , . Recurse on index 6: node 6 has value 3, left child index 13 = 10, right child index 14 = 12. Largest is 12 (index 14). Swap: , . Done.

  7. MAX-HEAPIFY(A, 1): Node 1 has value 1, left child index 3 = 17, right child index 4 = 16. Largest is 17 (index 3). Swap: , . Recurse on index 3: node 3 has value 1, left child index 7 = 14, right child index 8 = 8. Largest is 14 (index 7). Swap: , . Recurse on index 7: node 7 has value 1, left child index 15 = 2, right child out of bounds. , swap: , . Done.

  8. MAX-HEAPIFY(A, 0): Node 0 has value 4, left child index 1 = 17, right child index 2 = 13. Largest is 17 (index 1). Swap: , . Recurse on index 1: node 1 has value 4, left child index 3 = 14, right child index 4 = 16. Largest is 16 (index 4). Swap: , . Recurse on index 4: node 4 has value 4, left child index 9 = 7, right child index 10 = 5. Largest is 7 (index 9). Swap: , . Node 9 is a leaf. Done.

Final heap array:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
17 16 13 14 7 11 12 2 8 4 5 9 11 10 3 1

Verification: The root (17) is the largest. Each parent is its children. ✓

4.5. Extract the Maximum Repeatedly (Lecture 9, Task 2)

Extract the maximum 12 times from the following max-heap (0-based):

0 1 2 3 4 5 6 7 8 9 10 11
15 13 9 5 12 8 7 4 0 6 2 1
Click to see the solution

Key Concept: Each EXTRACT-MAX call: (1) save A[0] (the current maximum), (2) copy the last element A[heap-size - 1] to position 0, (3) decrement heap-size, (4) call MAX-HEAPIFY(A, 0) to restore the heap property.

The sequence of extracted maximums and the resulting heap roots are traced below. We show the root value after each heapify step.

Extraction 1: Remove 15. Move to root. Heap has 11 elements. - MAX-HEAPIFY(0): 1 → swap with 13 (index 1) → swap with 12 (index 4) → swap with 6 (index 9). Heap root is now 13.

Extraction 2: Remove 13. Move to root. Heap has 10 elements. - MAX-HEAPIFY(0): 2 → swap with 12 (index 4) → swap with 6 (index 9). Root is 12.

Extraction 3: Remove 12. Move to root. Heap has 9 elements. - MAX-HEAPIFY(0): 6 → swap with 9 (index 2) → swap with 8 (index 6). Root is 9.

Extraction 4: Remove 9. Move to root. Heap has 8 elements. - MAX-HEAPIFY(0): 0 → swap with 8 (index 6). Root is 8.

Extraction 5: Remove 8. Move to root. Heap has 7 elements. - MAX-HEAPIFY(0): 4 → swap with 7 (index 2). Root is 7.

Extraction 6: Remove 7. Move to root. Heap has 6 elements. - MAX-HEAPIFY(0): 0 → swap with 5 (index 1) → swap with 4 (index 3). Root is 6.

Extraction 7: Remove 6. Move to root. Heap has 5 elements. - MAX-HEAPIFY(0): 5 is already all children. Root is 5.

Extraction 8: Remove 5. Move to root. Heap has 4 elements. - MAX-HEAPIFY(0): 4 is largest. Root is 4.

Extraction 9: Remove 4. Move to root. Heap has 3 elements. - MAX-HEAPIFY(0): 0 → swap with 2 (index 1). Root is 2.

Extraction 10: Remove 2. Move to root. Heap has 2 elements. - MAX-HEAPIFY(0): 0 → swap with 1 (index 1). Root is 1.

Extraction 11: Remove 1. Move to root. Heap has 1 element. - MAX-HEAPIFY(0): single element, trivially a heap. Root is 0.

Extraction 12: Remove 0. Heap is now empty.

Result: Elements extracted in sorted order: 15, 13, 12, 9, 8, 7, 6, 5, 4, 2, 1, 0.

This sequence confirms the max-heap correctly produces elements in descending order, just as heapsort relies on.

4.6. Extract the Minimum from a Fibonacci Heap (Lecture 9, Task 3)

Extract the minimum from the Fibonacci heap whose root list (in left-to-right order) is: 23, 7, 3, 17, 24. Node 3 is H.min. The children of 3 are 18, 52, 38 (with 18 having child 39, and 38 having child 41). Node 17 has child 30. Node 24 has children 26, 46, where 26 has child 35.

Click to see the solution

Key Concept: FIB-HEAP-EXTRACT-MIN removes the minimum node, promotes all its children to the root list, then calls CONSOLIDATE to ensure all roots have distinct degrees.

Step 1 — Remove the minimum and promote children.

The minimum node is 3 (with degree 3: children 18, 52, 38). Remove 3 from the root list. Add 18, 52, 38 to the root list, clearing their parent pointers.

New root list: 23, 7, 18, 52, 38, 17, 24.

Step 2 — Consolidate.

Use auxiliary array (since ).

Scan roots and group by degree:

  • Node 23: degree 0. .
  • Node 7: degree 2 (children: …). .
  • Node 18: degree 1 (child 39). .
  • Node 52: degree 0. Conflict with . Link: 52 > 23, so 52 becomes child of 23. Now 23 has degree 1. Conflict with . Link: 23 > 18, so 23 becomes child of 18. Now 18 has degree 2. Conflict with . Link: 18 > 7, so 18 becomes child of 7. Now 7 has degree 3. .
  • Node 38: degree 1 (child 41). .
  • Node 17: degree 1 (child 30). Conflict with . Link: 38 > 17, so 38 becomes child of 17. Now 17 has degree 2. Conflict with : currently empty after the cascade above. .
  • Node 24: degree 2 (children 26, 46). Conflict with . Link: 24 > 17, so 24 becomes child of 17. Now 17 has degree 3. Conflict with . Link: 17 > 7, so 17 becomes child of 7. Now 7 has degree 4. .

Result. After consolidation, the root list contains only node 7 (with degree 4 and a large subtree beneath it). H.min = 7.

Answer: The extracted minimum is 3. The resulting Fibonacci heap has minimum 7 and H.n decremented by 1.

4.7. Perform Decrease-Key Operations (Lecture 9, Task 4)

Starting from the Fibonacci heap in Task 3 (before extraction), perform the following decrease-key operations in order: 1. Decrease key . 2. Decrease key .

Click to see the solution

Key Concept: After each decrease, if the new key violates the min-heap property (is less than the parent’s key), cut the node and move it to the root list. Apply cascading cut to the parent.

Initial state (from Figure 15): H.min = 3. Notable structure:

  • Node 24 has children 26 and 46. Node 26 has child 35.
  • No nodes are initially marked.

Operation 1: Decrease .

  1. Set .
  2. Parent of 46 is 24. Check: ? Yes — heap property violated.
  3. CUT(H, node_{15}, node_{24}): Remove 15 from 24’s child list (24’s degree decreases by 1). Add 15 to root list. Set , .
  4. CASCADING-CUT(H, node_{24}): Parent of 24 is not NIL (24 is a child of… check structure: 24 is in the root list originally, so its parent is NIL). Parent of 24 is NIL → stop.
  5. Check if ? No.

State after Operation 1: 15 is a new root. Node 24 now has one child (26, with child 35). Node 24 is not marked (it lost its first child and cascading cut found a NIL parent).

Note on cascading cut: Node 24 is originally in the root list with children 26 and 46. Its parent pointer is NIL. After cutting 46 (now 15), CASCADING-CUT(H, 24) is called. Since , the function returns immediately. Node 24 is not marked.

Operation 2: Decrease .

  1. Set .
  2. Parent of 5 (formerly 35) is 26. Check: ? Yes — heap property violated.
  3. CUT(H, node_5, node_{26}): Remove 5 from 26’s child list. Add 5 to root list. .
  4. CASCADING-CUT(H, node_{26}): Parent of 26 is 24. Is ? Yes (26 hasn’t lost a child before). So set . Stop.

State after Operation 2:

  • Root list now contains: 23, 7, 3, 17, 24, 15, 5.
  • Node 26 is marked (it lost child 35→5).
  • Node 24 still has children 26 (marked). H.min = 3 (unchanged since ).

Summary of cuts performed: One regular cut (46→15 cut from 24), one regular cut (35→5 cut from 26). Node 26 is now marked. The cascading cut mechanism did not need to climb further in this example.

4.8. Construct a Fibonacci Heap of Height (Lecture 9, Task 5)

Show that for any , there exists a sequence of operations such that a Fibonacci heap has elements and height (i.e., a single tree that is a long linear chain).

Click to see the solution

Key Concept: The height of trees in a Fibonacci heap is normally bounded by due to the mark/cascading-cut mechanism. However, this bound relies on no node losing two children. We can exploit DECREASE-KEY to trigger cascading cuts that deliberately build a long chain.

Construction idea. We alternate between building a tree of bounded degree (via inserts + extract-min) and then using DECREASE-KEY to strip its internal nodes one level at a time.

The following protocol builds a chain of height :

Base case (): Insert two elements, say 100 and 200. Extract-min: 100 becomes root, 200 becomes its child (degree 1 after consolidation). We have a chain of height 1.

Inductive step: Suppose we have a chain (root with at depth ). We want to add a level.

  1. Insert a new minimum element .
  2. Extract-min: is removed; consolidation may restructure things. By carefully choosing the key values, we can ensure the tree of depth is preserved.
  3. After the extract-min, insert fresh elements (with large keys so they don’t affect the minimum). Extract-min from this combined forest — consolidation links trees of equal degree, extending the chain.

Concrete example demonstrating a chain of height 3:

  1. Insert 45. Insert 23. Extract-min: forest and consolidate (after promoting 23’s children, which are none) → after consolidation: tree 23→45. Chain of height 1.
  2. Insert 1. (Root list: 1, 23→45.) Extract-min: Remove 1. Add children of 1 (none). Root list: 23→45. Consolidate: only one tree. H.min = 23.

The cleaner general approach is to repeatedly apply the following pattern to create longer and longer binomial-tree-like chains, then use decrease-key to strip all but one branch:

  1. Perform a sequence of insert + extract-min pairs to create a binomial tree of height and nodes.
  2. Apply DECREASE-KEY to strip all but the leftmost branch of , reducing it to a chain of height with nodes.

After step 2, we have a chain where every internal node () is marked (it lost one child due to the decrease-key operations). Adding one more node as a child of (via insert + extract-min), and then applying DECREASE-KEY on a deeper node triggers a cascading cut that runs all the way up, producing a new valid tree.

Conclusion. By a careful sequence of insert and extract-min operations followed by decrease-key operations, we can arrange for a Fibonacci heap of elements to contain a single tree that is a path (chain) of height . This shows that the degree bound is tight under adversarial operation sequences that deliberately exploit the mark mechanism.

Answer: Yes, such a sequence exists. The construction relies on building a “degenerate” chain by alternating consolidation with cascading cuts, showing that the height is achievable (and thus the amortized analysis is needed; worst-case per-operation analysis alone would give for EXTRACT-MIN).